package everydayone.minIncrement;

import java.util.Arrays;

/**
 * @Date 2020/03/22
 * @author 王光浩
 * @Thinking 先排序后统计
 * @Analysis 时间复杂度O（nlogn），空间复杂度O（logn）——n是数组中元素的个数
 * @ 思路：首先将数组进行排序，然后从小至大遍历数组，这样数组整体上是递增的，但是可能会存在多个值相等的情况
 * @       如果我们想获取最小的操作次数，这些相等元素最好是按照递增数列的形式，这样我们就只需要确定相等元素的
 * @       的第一个元素值应该是多少即可，这时我们需要定义一个变量保存前面所有已经形成唯一数组的最大值，然后将
 * @       这个最大值与相等元素的第一个进行比较，等差数列的第一项就是两者中的最大值，这时我们可以使用等差数列的
 * @       的求和来求等差数列的和，然后将获取的和减去原本子数组的和，这样就可以获取操作数。
 */
public class MyMethodOne {
	 public int minIncrementForUnique(int[] A) {
		 if(A.length==0)return 0;
		 int count=0;   //统计操作次数
		 Arrays.sort(A); //对数组进行排序，时间复杂度O（nlogn）
		 int max=Integer.MIN_VALUE;
		 int value=A[0];
		 int num=1;
		 //利用等差数列来获取最小次数
		 for(int i=1;i<A.length;i++) {
			 if(A[i]!=value) {
				 int first=(value>max)?value:max+1;
				 count+=(first*num+num*(num-1)/2-num*value);
				 max=first+num-1;
				 num=1;
				 value=A[i];
			 }
			 else
				 num++;
		 }
		 int first=(value>max)?value:max+1;
		 count+=(first*num+num*(num-1)/2-num*value);
		 return count;
	 }
}
